package leetcode;

import java.util.Arrays;

public class NextPermutation {

	public static void main(String[] args) {
		NextPermutation object = new NextPermutation();
		int[] nums = {1, 5};
		object.nextPermutation(nums);
		for (int i = 0; i < nums.length; i++) {
			System.out.print(nums[i] + " ");
		}
	}
	
	public void nextPermutation(int[] nums) {
        if(nums == null || nums.length <= 0){
            return ;
        }
        int index;
        for(int i = nums.length - 1; i >= 1; i--){
            if(nums[i - 1] < nums[i]){
            	index = moreThan(nums, i, nums.length, nums[i - 1]);
            	System.out.println("index" + index);
                swap(nums, i - 1, index);
                Arrays.sort(nums, i, nums.length);
                for (int j = 0; j < nums.length; j++) {
        			System.out.print(nums[j] + " ");
        		}
                return;
            }
        }
        for (int i = 0; i < nums.length / 2; i++) {
			swap(nums, i, nums.length - 1 - i);
		}
    }

	//找到第一个大于key的下标
	public int moreThan(int[] nums, int fromIndex, int toIndex, int key){
		for (int i = toIndex - 1; i >= fromIndex; i--) {
			if(nums[i] > key){
				return i;
			}
		}
		return -1;
	}
	
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
